package lc;

import java.util.Arrays;

import org.junit.Test;

public class Ex416 {
    class Solution {
        //分割两个相同的部分（求sum/2)
        public boolean canPartition(int[] nums) {
            int sum = 0, n = nums.length;
            for (int i = 0; i < n; i++) {
                sum += nums[i];
            }
            int tar = sum / 2;
            if (tar * 2 != sum) {
                return false;
            }
            //i...
            boolean[] f = new boolean[tar + 1];
            //f[n][0] 可以得到，f[n][i] (i > 0不可以得到)
            f[0] = true;
            for (int i = n - 1; i >= 0; i--) {
                for (int j = tar; j >= nums[i]; j--) {
                    f[j] = f[j] || f[j - nums[i]];
                }
                System.out.println(Arrays.toString(f));
            }

            return f[tar];
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,5};
        System.out.println(s.canPartition(nums));
    }
}
